#include<stdio.h>

void HeapSort(int* a, int n);

void PrintArray(int* a, int n)
{
    int i = 0;
    for(i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void Swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while(child < n)
    {
        if(child + 1 < n && a[child + 1] > a[child])
        {
            ++child;
        }

        if(a[child] > a[parent])// 降序
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else 
        {
            break;
        }
    }
}

void HeapSort(int* a, int n)
{
    int i = 0;
    // 直接建堆
    for(i = (n - 1 - 1)/2; i >= 0; --i)
    {
        AdjustDown(a, n, i);
    }

    // 升序建大堆
    int end = n - 1;
    while(end >= 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end , 0);
        --end;
    }
}

void TestHeapSort()
{
    int a[] = {1,4,2,6,8,7,3,9,0,5};
    PrintArray(a, sizeof(a)/sizeof(a[0]));
    HeapSort(a, sizeof(a)/sizeof(a[0]));
    PrintArray(a, sizeof(a)/sizeof(a[0]));
}


int main()
{
    TestHeapSort();

    return 0;
}
